Digital communication systems have many ways of transmitting data through noisy communication channels that help facilitate recovery of the data at the receiver. One conventional method involves convolutionally encoding the data prior to transmission. In such a system, convolutional encoding may be performed after the addition of error correction codes and compression of the data. The convolutional encoding process embeds bits in the data stream resulting in a greater number of bits for transmission, depending on the rate of the coder.
In a digital wireless system, for example, in-phase (I) signals and qudrature-phase (Q) signals may be generated from the convolutionally encoded data and modulated onto a carrier frequency for transmission to a receiver. In this way, a wireless communication device can transmit digital information, including voice and data, over a noisy channel to another wireless communication device via a base station, for example.
When receiving communications, the receiver performs a frequency conversion on the received signals and generates the I and Q signals by quadrature detection. An estimate of the original convolutionally encoded data may be reproduced from the I and Q signals. Convolutional decoding may then be carried out to recover the original data. Convolutional encoding provides for error correcting because only some of the possible sequences are valid outputs from the encoder. These sequences correspond to possible paths through a trellis. In digital communication systems, convolutional encoding is performed to help assure that data can be recovered even when the communication environment becomes poor. For example, wireless communication devices are often used in environments with poor or noisy transmission characteristics, such as in a car where distortion occurs in the received signals. A convolutional decoder is conventionally used to reduce bit error rates and enhance performance.
One common convolutional decoding process is known as Viterbi decoding. Viterbi decoding detects a most likely transition path among multiple symbols by estimating the probabilities of transitions in convolutionally encoded serial input data. Decoding of the input data is based on the detected most likely transition path. Accurate decoding results can be obtained even in the case where a sudden large change in the signal level of input data occurs.
A Viterbi decoder is used for maximum likelihood decoding of convolutional codes. From many known code sequences of possible input code sequences, a code sequence is selected as a maximum likelihood code sequence. The selected code sequence may be generated by a convolutional encoder that generates an output sequence closest in code distance to the received data. The maximum likelihood code sequence is referred to as the maximum likelihood path. The decoded data may be obtained from this path. In a Viterbi decoding process, a combination of maximum likelihood branches out of several respective branches reaching the respective encoder states is selected along with a surviving path. This process continues until a predetermined path length is obtained and then a maximum likelihood surviving path is traced back to decode the input signal.
A Viterbi decoder generally includes a branch metric calculation unit and an add-compare-select (ACS) unit. The branch metric calculation unit calculates branch metrics (i.e., distances between the input code sequences and code sequences predicted in respective branches). The ACS unit calculates accumulated path metrics and selects surviving paths. A path metric transition diagram may be prepared based on a trellis diagram.
A convolutional encoder takes k bits at a time and produces groups of n output bits, where n is greater than k. When k is the input data rate and n is the output data rate, the code is known as a k/n code. For example, an encoder that takes one bit at a time and produces two output bits is called a ½ rate coder, while an encoder that takes two bits at a time and produces three bits is a ⅔ rate coder. Different ACS operations are conventionally required for code rates of a different k. For example, when k is one, two-way ACS operations are generally performed because there are two possible paths to each state. When k is two, four-way ACS operations are generally performed because there are four possible paths to each state. In general, a k/n coder has 2k possible paths into each encoder state and 2k way ACS operations are required in the decoder.
The ACS elements of a conventional decoder add a branch metric value to a previous path metric for two or more different paths, then compare the results and select one of the results as the new path metric. ACS elements may also store the branch decision. Normally, a Viterbi decoder is designed to select the best (e.g., the minimum) value of the ACS operation results. Because the branch metrics are positive values, the path metric will continue to grow unbounded through each iteration through the trellis. If the path metric is implemented with a fixed number of bits, which is generally the case for a realizable design, all the path metric values will eventually overflow. The difference between the maximum path metric value and the minimum path metric value is bounded by the maximum branch metric and the decoding depth. This difference has been used by conventional decoders to avoid the overflow problem.
In some conventional decoders, the minimum value of all the path metrics generated within one trellis iteration of the Viterbi algorithm is subtracted from all path metrics before performing the ACS operations. Because the path metrics are fed back to generate the next set of path metrics, only one register exists in the data path. This allows the ACS elements to perform their operation within one clock-cycle. However, to maintain a one clock-cycle processing time, the rescaling circuit must operate without additional registers. This unfortunately increases the processing delay of the ACS elements and decreases the maximum clock-rate at which the ACS element may operate. The additional adders required in the ACS elements of these conventional decoders also increases the circuit area required by the ACS elements on a semiconductor die.